/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //储存中序遍历索引
    HashMap<Integer,Integer> map = new HashMap<>();
    int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0;i<inorder.length;i++) {
            map.put(inorder[i],i);
        }
        return recur(0,0,preorder.length-1);
    }
    private TreeNode recur(int rootIndex, int leftIndex,int rightIndex) {
         if(leftIndex > rightIndex)  {
             return null;
         }
        //建立前序遍历第一个结点(根节点)
        TreeNode root = new TreeNode(preorder[rootIndex]);
        int i = map.get(preorder[rootIndex]);
        root.left = recur(rootIndex+1,leftIndex,i-1);
        root.right = recur(i- leftIndex + rootIndex + 1,i + 1,rightIndex);
        return root;
    }
}